package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Stack;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月15日
*时间：下午5:10:24
*/
public class Q362 {
    /**
     * @param nums: A list of integers.
     * @return: The maximum number inside the window at each moving.
     */
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> rs = new ArrayList<>();
        if (nums == null || nums.length <= 0) {
            return rs;
        }
        Stack<Integer> s = new Stack<>();
        s.push(nums[0]);
        int point = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= s.peek()) {
                s.push(nums[i]);
                point = i;
            } else {
                if (i - point >= k) {
                    point = findMax(nums, point, i);
                    s.push(nums[point]);
                } else {
                    s.push(s.peek());
                }
            }
        }
        int n = nums.length;
        while (n >= k) {
            rs.add(0, s.pop());
            n--;
        }
        return rs;
    }

    private int findMax(int[] nums, int point, int i) {
        int point1 = point + 1;
        for (int j = point + 1; j <= i; j++) {
            if (nums[j] >= nums[point1]) {
                point1 = j;
            }
        }
        return point1;
    }

    @Test
    public void testA() {
        int nums[] = { 1, 2, 7, 7, 8, 3, 1, 0 };
        System.out.println(maxSlidingWindow(nums, 2));
    }
}
